package com.zp.self.module.level_4_算法练习.数学.位运算;

/**
 * @author By ZengPeng
 */
public class 力扣_201_数字范围按位与 {
    //测试
    public static void main(String[] args) {
        //输出一下1-100的二进制字符串
        for (int i = 0; i < 101; i++) {
            System.out.println(i+"-->" +Integer.toBinaryString(i));
        }
//            System.out.println(2147483646+"-->" +Integer.toBinaryString(2147483646));
//            System.out.println(2147483647+"-->" +Integer.toBinaryString(2147483647));

//        System.out.println(new 力扣_201_数字范围按位与().rangeBitwiseAnd(5,7));
//        System.out.println(new 力扣_201_数字范围按位与().rangeBitwiseAnd(0,0));
//        System.out.println(new 力扣_201_数字范围按位与().rangeBitwiseAnd(1,2147483647));
//        System.out.println(new 力扣_201_数字范围按位与().rangeBitwiseAnd(2147483646,2147483647));
//        System.out.println(new 力扣_201_数字范围按位与().rangeBitwiseAnd(2147483645,2147483646));
    }

    /**
    题目：给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

     示例 1：
     输入：left = 5, right = 7
     输出：4

     示例 2：
     输入：left = 0, right = 0
     输出：0

     示例 3：
     输入：left = 1, right = 2147483647
     输出：0

    分析：【P 💜💜】
       1.直接遍历：会超时吧？ 21亿个数你说呢(ง •_•)ง
       2.分析：同为1才为1 ，只要有0 就为0 总共就32位【-1个符号位】
                思维a.使用位图记录32位中出现0 的个数，左右指针移动
            -- 太麻烦了，太慢了吧
                思维b.left & right  <=left  而且很容易给干到0去了
            --执行用时：674 ms, 在所有 Java 提交中击败了5.03%的用户
                思维c.如果范围中有个数 x=2的n次方时，就只剩一个1了 这时与x & x-1 妥妥的为0啊！  所以转换一下 left <= right/2
            --执行用时：3 ms, 在所有 Java 提交中击败了100.00%的用户
                思维d. left < 2^x <= right 时 也可以直接返回0了
            --emmmm  上面已经击败100% 的人了，那就这样吧...
       官方：还有一个位移相关的算法叫做「Brian Kernighan 算法」，它用于清除二进制串中最右边的 1。
            每次对 number 和 number−1 之间进行按位与运算后，number 中最右边的 1 会被抹去变成 0。
            例如：   输入 9，12
                11-->1011    12 & 11   =8  ，此时不用再& 9 、10
                12-->1100    1000
            他们的二进制：
             9--> 1001
             10-->1010
             11-->1011
             12-->1100


    边界值 & 注意点：
       1.2147483646  2147483647   答案： 2147483646  ，错误原因：left =2147483647  时++left溢出了
     **/
    public int rangeBitwiseAnd(int left, int right) {
        // 官方：每次对 number 和 number−1 之间进行按位与运算后，number 中最右边的 1 会被抹去变成 0。
        if(left <= right/2) return 0;
        while (left<right){
            right = right&(right-1);
        }
        return right;

        //2.思维c.如果范围中有个数 x=2的n次方时，就只剩一个1了 这时与x & x-1 妥妥的为0啊！  所以转换一下 left <= right/2
        /*if(left <= right/2)return 0;
        if(2147483646==left || 2147483647 ==left) return left;
        int res=left;
        while (++left<=right && res!=0){
            res = (res&left);
            res = (res&right--);
        }
        return res;*/
    }
}
